package com.cyy.tree;

import java.util.Comparator;

/**
 * BST 二叉搜索树
 * @author 会玩的洋洋
 * @since 2022-02-24
 * @param <E>
 */
public class BST<E> extends BinaryTree<E> {
    /**
     * 比较器  由构造中实现的Comparator中的compare方法进行说明比较方式
     */
    protected Comparator<E> comparator;

    public BST() {
        this(null);
    }

    public BST(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    /**
     * 添加节点
     * 进行遍历比较添加
     * @param element 添加元素
     */
    public void add(E element) {
        this.elementNotNullCheck(element);
        // 首次添加
        if (root == null) {
            root = createNode(element, null);
            ++size;

            afterAdd(root);
            return;
        }
        Node<E> node = root;
        Node<E> parent = root;
        int cmp = 0;
        // 循环比较
        while (node != null) {
            cmp = compare(node.element, element);
            // 记录父节点
            parent = node;
            // 如果 node.element > element 则向左移动
            if (cmp > 0) {
                node = node.left;
            } else if (cmp < 0) {
                // 如果 node.element < element 则向右移动
                node = node.right;
            } else {
                // 相等 则覆盖原来的 element
                node.element = element;
                return;
            }
        }
        Node<E> newNode = createNode(element, parent);
        if (cmp > 0) {
            parent.left = newNode;
        } else {
            parent.right = newNode;
        }
        ++size;

        afterAdd(newNode);
    }

    /**
     * 删除节点
     * @param element 要删除节点的元素
     * @return E
     */
    public E remove(E element) {
        // 因为二叉树中的元素没有重复元素，因此首先要找到对应元素的节点
        return remove(node(element));
    }

    /**
     * 通过 node 节点删除节点
     * @param node 要删除的节点
     * @return E
     */
    private E remove(Node<E> node) {
        // 如果传入的 node 为 null 则 返回 null
        if (node == null) {
            return null;
        }
        --size;
        E oldElement = node.element;
        // 先判断是否是度为 2 的节点 如果是，则找前驱或者后继对他进行覆盖，再删除叶子节点即可
        if (node.hasTwoChildren()) {
            Node<E> successor = successor(node);
            node.element = successor.element;
            node = successor;
        }
        Node<E> replaceNode = node.left != null ? node.left : node.right;
        // 更改父子节点指向
        if (replaceNode != null) {
            replaceNode.parent = node.parent;
            if (node.parent == null) {
                // 删除的根节点
                root = replaceNode;
            } else if (node.parent.left == node) {
                // 说明 node 是父节点的 左子节点
                node.parent.left = replaceNode;
            } else {
                node.parent.right = replaceNode;
            }

            afterRemove(replaceNode);
        } else {
            // 如果找不到替代节点, 说明删除的是叶子节点
            Node<E> parent = node.parent;
            if (parent == null) {
                // 如果删除的是根节点 并且没有替代元素，则删除的是最后一个节点
                root = null;
            } else if (parent.left == node) {
                // 删除的是左子树的叶子节点
                parent.left = null;
            } else {
                parent.right = null;
            }

            afterRemove(node);
        }
        return oldElement;
    }

    /**
     * 判断树中是否存在该元素
     * @param element 查找的元素
     * @return boolean
     */
    public boolean contains(E element) {
        return node(element) != null;
    }

    /**
     * 添加之后的操作 （为 AVL树 和 红黑树的平衡提供方法）
     * @param node 添加的节点
     */
    protected void afterAdd(Node<E> node) {

    }

    /**
     * 删除之后的操作 （为AVL树 和 红黑树做准备）
     * @param node 删除的节点
     */
    protected void afterRemove(Node<E> node) {

    }

    /**
     * 创建节点  为后续 AVL树 和 红黑树 创建对应的节点提供方法
     * @param element 元素
     * @param node 父节点
     * @return Node<E>
     */
    protected Node<E> createNode(E element, Node<E> node) {
        return new Node<>(node, element);
    }

    /**
     * 通过元素值 查询目标节点
     * @param element 元素值
     * @return Node<E>
     */
    private Node<E> node(E element) {
        // element 不可以为 null 为 null 无法比较大小
        if (element == null) {
            return null;
        }
        Node<E> node = root;
        int cmp = 0;
        // 循环遍历 比较大小， 根据搜索树性质进行检索
        while (node != null) {
            cmp = compare(node.element, element);
            if (cmp > 0) {
                node = node.left;
            } else if (cmp < 0) {
                node = node.right;
            } else {
                return node;
            }
        }
        // 没有找到元素
        return null;
    }

    private int compare(E e1, E e2) {
        // 如果比较器不为 null 则用比较器 比较
        if (comparator != null) {
            this.comparator.compare(e1, e2);
        }
        // 如果传入的比较器为 null 则需要传入的 Element 实现 Comparable这个比较类
        return ((Comparable<E>)e1).compareTo(e2);
    }

    /**
     * 检查元素是否为 null
     * @param element 待检查元素
     */
    private void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("ELEMENT IS NOT BE EMPTY !!");
        }
    }
}
